package org.example.Soution003;

import java.util.ArrayList;
import java.util.List;

public class MidumInStream {
    public static void main(String[] args) {
        MedianFinder mf=new MedianFinder();
        mf.addNum(-1);
        System.out.println(mf.findMedian());
        mf.addNum(-2);
        System.out.println(mf.findMedian());
        mf.addNum(-3);
        System.out.println(mf.findMedian());
        mf.addNum(-4);
        System.out.println(mf.findMedian());
        mf.addNum(-5);
        System.out.println(mf.findMedian());
    }
}

class MedianFinder {
    //什么样的数据结构？
    List<Integer> list;

    public MedianFinder() {
        //初始化这个数据结构
        list = new ArrayList<Integer>();
    }

    public void addNum(int num) {
        //添加元素？或者做一些预备工作？
        //使用list需要做预备工作，计划使用二分找到插入位置
        if(list.size()==0){
            list.add(num);
            return;
        }
        int end=list.size()-1,start=0;
        while(end>=start){
            int mid=start+(end-start)/2;
            if(list.get(mid)>num){
                end=mid-1;
            }else if(list.get(mid)<num){
                start=mid+1;
            }else{
                start=mid;
                break;
            }
        }
        list.add(start,num);
    }

    public double findMedian() {
        //找到中位数并返回
        if(list.size()%2==0){
            int mid=list.size()/2;
            return ((list.get(mid)+list.get(mid-1))/2.0);
        }else{
            return (double)list.get(list.size()/2);
        }
    }
}
